
#include "graph.h"
#include "utils.h"
#include "set.h"
#include "sortstrategy.h"
#include "bubblesort.h"
#include "mergesort.h"
#include "heapsort.h"
#include "stdsort.h"
#include "algostrategy.h"
#include "kruskals.h"
#include "algo.h"

#include <stdio.h>


using std::vector;

// Doing the sorting as a separate step rather than using a priority queue gives a huge hit
// to performance, you'll need to know why for assignment 2
void Kruskals::compute(vector<Vertex> &vertexVector, List &edgeList, DataStrategy *s)
{
	SortStrategy* ss;
	ss = dynamic_cast<SortStrategy*>(s);
	if(!ss)		
	{
		std::cerr << "DataStrategy is not a SortStrategy" << std::endl;
		exit(EXIT_FAILURE);
	}
	
	//Sorter sorter(type);
	Sorter sorter(ss);
	
	//Edge *edgeArray = new Edge[(size * (size - 1)) / 2];
	vector <Edge> edgeVector;
	int size = (int) vertexVector.size();
	
	// Set could be made a member of the vertex class, but that breaks modularity
	// slightly, since sets are unique to Kruskal's in the program, this is where
	// they should be, also, an array of pointers to sets is slightly faster	
	Set **sets = new Set*[size];
	for (int i = 0; i < size; i++)
		sets[i] = makeSet();

	//int pos = 0;
	for (int i = 0; i < size; i++)
		for (int j = i+1; j < size; j++)
			//edgeArray[pos++] = Edge(vertexArray[i], vertexArray[j], i, j);
			edgeVector.push_back(Edge(vertexVector[i], vertexVector[j], i, j));
			
	beginTimer();
	//edgeArray = sorter.sort(edgeArray, (size * (size - 1)) / 2);
	sorter.sort(edgeVector);
	endTimer();
	std::cout << "Sorting time: " << getTime() << " s\n";
	int currPos = 0;

	while (edgeList.getSize() < size - 1)
	{
#if DEBUG
		if (currPos >= (size * (size - 1)) / 2)
			std::cerr << "Out of bounds of sorted array\n";
#endif

		//Edge &minEdge = edgeArray[currPos++];
		Edge &minEdge = edgeVector[currPos++];
		int index1 = minEdge.index1;
		int index2 = minEdge.index2;
		
#if DEBUG
		if (index1 < 0 || index2 < 0)
			std::cerr << "Invalid edge at position " << currPos << "\n";
#endif

		if (findParent(sets[index1]) != findParent(sets[index2]))
		{
			edgeList.add(vertexVector[index1], vertexVector[index2], index1, index2);
			unionSets(sets[index1], sets[index2]);
		}
	}
	
	//delete [] edgeArray;

	for (int i = 0; i < size; i++)
		delete sets[i];
	delete [] sets;

}

